// 先选择极端分配节点，选择的依据是按照边缘节点最大被打满的程度（0 ~ 1.0），按照打满程度z-score标准化，选取标准化后最大的（边缘节点，时刻）
// 选择好边缘节点后，按照流的带宽和最大来优先分配某个流的请求，分配该流时，按照大带宽到小带宽的顺序进行分配，（不把边缘节点的带宽全打满，预留0.05，避免过量的溢出导致分数变差）
// 并同时更新同时刻其他边缘节点被打满的程度，及其标准化需要的均值-方差
// 将某个时刻选择为极端分配节点后，再下一时刻设置为缓冲时刻，缓冲时刻占一个极端分配次数，但是在极端分配流量那一步先不分配流量，缓冲时刻的思想是提分的关键！！！！
// 缓冲时刻的前一个极端分配时刻可以尽量的拉满流量，选择极端分配节点时应当尽量分配多个连续的极端分配时刻再紧跟一个缓冲时刻，这样可以尽量的利用带宽上限
// 极端节点设置好之后，给极端节点的前一时刻和后一时刻增加一个带宽膨胀比例，使得下次选极端分配节点时，前一时刻和后一时刻更容易被选定为极端分配节点
// 使得极端分配节点是连续分配的，共享一个缓冲节点，使得可以吸收更多大流量
// 极端分配完成后，按照打满比例低为原则分配剩余流量，对于缓冲节点，其打满比例是由下一时刻的总流量（分配流量和继承流量之和）来计算

// 官方线下数据集分数: 
//     初解：total_score:149985 edge_site_score:68195 center_site_score:81790
//     优化后：total_score:105545 edge_site_score:43580 center_site_score:61965
// 训练赛线上分数：1019702

#include <vector>
#include <unordered_map>
#include <algorithm>

#include "constants.h"
#include "classes.h"
#include "tools.h"
#include "data_io.h"
#include "init_solution.h"
#include "visualizer.h"

using namespace std;

//////////////////////////////////////////////////////////////////////////////////////
// start: 前置工具
//////////////////////////////////////////////////////////////////////////////////////
class _HeapNode
{
public:
    int t;
    int heap_idx;
    int value;
    _HeapNode(int t, int value);
};
_HeapNode::_HeapNode(int t, int value)
{
    this->t = t;
    this->value = value;
}

bool _heap_node_cmp(_HeapNode *x, _HeapNode *y)
{
    return x->value < y->value;
};

class LargestUpdater
{
public:
    vector<_HeapNode *> heap_vec;
    vector<_HeapNode *> t_index_vec;
    int size;

    LargestUpdater(vector<int> &value_arr);

    _HeapNode *head();

    _HeapNode *at(int t);

    void pop_head();
    void pop_t(int t);
    void update(int t, int diff);
    bool is_poppid(int t);

private:
    void _adjust_lower(_HeapNode *target_node);
    void _adjust_higher(_HeapNode *target_node);
    void _swap_node(_HeapNode *n1, _HeapNode *n2);
};

LargestUpdater::LargestUpdater(vector<int> &value_arr)
{
    int T = value_arr.size();
    this->size = T;
    this->heap_vec.reserve(T);
    this->t_index_vec.reserve(T);

    for (int t = 0; t < T; t++)
    {
        _HeapNode *node = new _HeapNode(t, value_arr[t]);
        this->heap_vec.push_back(node);
        this->t_index_vec.push_back(node);
    }

    make_heap(this->heap_vec.begin(), this->heap_vec.end(), _heap_node_cmp);

    for (int _i = 0; _i < T; _i++)
    {
        this->heap_vec[_i]->heap_idx = _i;
    }
}

_HeapNode *LargestUpdater::head()
{
    if (this->size)
    {
        return heap_vec[0];
    }
    else
    {
        return NULL;
    }
}

_HeapNode *LargestUpdater::at(int t)
{
    return this->t_index_vec[t];
}

void LargestUpdater::pop_head()
{
    if (this->size)
    {
        _HeapNode *head = heap_vec[0];
        _HeapNode *tail = heap_vec[--this->size];
        this->_swap_node(head, tail);
        this->_adjust_lower(tail);
    }
}

void LargestUpdater::pop_t(int t)
{
    if (this->size)
    {
        _HeapNode *node = this->t_index_vec[t];
        _HeapNode *tail = heap_vec[--this->size];
        this->_swap_node(node, tail);
        this->_adjust_lower(tail);
        this->_adjust_higher(tail);
    }
}

bool LargestUpdater::is_poppid(int t)
{
    _HeapNode *node = this->t_index_vec[t];
    return node->heap_idx >= this->size;
}

void LargestUpdater::update(int t, int diff)
{
    _HeapNode *node = this->t_index_vec[t];
    if (node->heap_idx >= this->size)
    {
        cout << "ERROR: unsupport update poppid value" << endl;
        throw exception();
    }

    node->value += diff;
    if (diff < 0)
    {
        this->_adjust_lower(node);
    }
    else
    {
        this->_adjust_higher(node);
    }
}

void LargestUpdater::_adjust_lower(_HeapNode *target_node)
{
    _HeapNode *left_child = target_node;
    _HeapNode *right_child = target_node;

    int left_child_idx = target_node->heap_idx * 2 + 1;
    int right_child_idx = target_node->heap_idx * 2 + 2;

    if (left_child_idx < this->size)
    {
        left_child = this->heap_vec[left_child_idx];
    }
    if (right_child_idx < this->size)
    {
        right_child = this->heap_vec[right_child_idx];
    }

    if (left_child->value > right_child->value)
    {
        if (left_child->value > target_node->value)
        {
            this->_swap_node(target_node, left_child);
            this->_adjust_lower(target_node);
        }
    }
    else
    {
        if (right_child->value > target_node->value)
        {
            this->_swap_node(target_node, right_child);
            this->_adjust_lower(target_node);
        }
    }
}

void LargestUpdater::_adjust_higher(_HeapNode *target_node)
{
    if (!target_node->heap_idx)
    {
        return;
    }
    int parent_idx = (target_node->heap_idx - 1) / 2;
    _HeapNode *parent_node = this->heap_vec[parent_idx];
    if (target_node->value > parent_node->value)
    {
        this->_swap_node(target_node, parent_node);
        this->_adjust_higher(target_node);
    }
}

void LargestUpdater::_swap_node(_HeapNode *n1, _HeapNode *n2)
{
    this->heap_vec[n1->heap_idx] = n2;
    this->heap_vec[n2->heap_idx] = n1;
    int _tmp_idx = n1->heap_idx;
    n1->heap_idx = n2->heap_idx;
    n2->heap_idx = _tmp_idx;
}

//////////////////////////////////////////////////////////////////////////////////////
enum AssignFlag //带宽类型
{
    CAREFUL, // 谨慎分配节点
    BUFFER,  // 高流量缓冲节点
    RADICAL  // 极端分配节点
};

class TAssignState //用来记录t时刻的带宽分配状态
{
public:
    AssignFlag site_big_bw_flag_arr[MAX_N];
    bool site_expanded_near_radical[MAX_N] = {false};

    TAssignState(TDemand *tdemand);
};

TAssignState::TAssignState(TDemand *tdemand)
{
    fill(this->site_big_bw_flag_arr, this->site_big_bw_flag_arr + MAX_N, CAREFUL);
};

vector<TAssignState *> _init_assign_state_vec()
{
    vector<TAssignState *> assign_state_vec;
    assign_state_vec.reserve(T);
    for (auto &tdemand : demand_info.demand_vec)
    {
        assign_state_vec.push_back(new TAssignState(tdemand));
    }
    return assign_state_vec;
}
//////////////////////////////////////////////////////////////////////////////////////
class SiteLargestTDemandManager //用于维护站点大流量排序
{
public:
    vector<LargestUpdater *> site_largest_tdemand_updater;
    vector<StdNormalizer *> site_demand_normalizer;
    vector<int> site_big_bw_remained_count;
    vector<TAssignState *> *assign_state_vec;
    list<tuple<int, int>> next_iter_buffer;
    double expansion_rate_near_radical = expansion_rate_near_radical;

    SiteLargestTDemandManager(vector<TAssignState *> *assign_state_vec, int min_stream, double expansion_rate_near_radical, int big_bw_drop_num);
    void next(int &t, int &site_id, int &largest_demand);
    void fetch_next();
    void decrease_demand_heap(int t, int (&site_demand_decrement)[MAX_N]);
    void increase_inherit_to_next_t(int t, int site_id, int site_allo_bw);
    void clear_site(int site_id);
};

SiteLargestTDemandManager::SiteLargestTDemandManager(vector<TAssignState *> *assign_state_vec,
                                                     int min_stream, double expansion_rate_near_radical, int big_bw_drop_num)
{
    this->assign_state_vec = assign_state_vec;
    this->expansion_rate_near_radical = expansion_rate_near_radical;
    vector<vector<int>> site_tdemand_matrix(N, vector<int>(T, 0));

    // 计算每个时刻边缘节点最大需求量
    for (auto &tdemand : demand_info.demand_vec)
    {
        int t = tdemand->t;
        for (int client_id = 0; client_id < M; client_id++)
        {
            int client_large_deamnd_sum = 0;
            for (int stream_id = 0; stream_id < tdemand->P; stream_id++)
            {
                int demand_bw = tdemand->demand_bw_matrix[stream_id][client_id];
                if (demand_bw > min_stream)
                {
                    client_large_deamnd_sum += demand_bw;
                }
            }

            for (auto &site_id : client_info.client_to_sites[client_id])
            {
                site_tdemand_matrix[site_id][t] += client_large_deamnd_sum;
            }
        }
    }

    int big_bw_num = (T - ceil(QUANTILE * T)) - big_bw_drop_num; // 包括极端分配和缓冲分配节点数量

    for (int site_id = 0; site_id < N; site_id++)
    {
        vector<int> &demand_arr = site_tdemand_matrix[site_id];
        StdNormalizer *normalizer = new StdNormalizer();

        double bw_upper = site_info.site_bw_upper[site_id];
        for (auto &demand_bw : demand_arr)
        {
            double full_rate = min(demand_bw / bw_upper, 1.0); //站点带宽能被打满的程度，最大为1.0
            normalizer->add(full_rate);
        }

        LargestUpdater *largest_updater = new LargestUpdater(demand_arr);

        if (largest_updater->head()->value)
        {
            this->site_big_bw_remained_count.push_back(big_bw_num);
        }
        else
        {
            this->site_big_bw_remained_count.push_back(0);
        }

        this->site_demand_normalizer.push_back(normalizer);
        this->site_largest_tdemand_updater.push_back(largest_updater);
    }
};

void SiteLargestTDemandManager::next(int &t, int &site_id, int &largest_demand)
{
    if (!this->next_iter_buffer.empty())
    {
        auto &front = this->next_iter_buffer.front();
        t = get<0>(front);
        site_id = get<1>(front);
        this->next_iter_buffer.pop_front();

        LargestUpdater *largest_updater = this->site_largest_tdemand_updater[site_id];
        _HeapNode *node = largest_updater->at(t);
        largest_demand = node->value;
        largest_updater->pop_t(t);

        StdNormalizer *normalizer = this->site_demand_normalizer[site_id];
        double bw_upper = site_info.site_bw_upper[site_id];
        double full_rate = min(largest_demand / bw_upper, 1.0);
        normalizer->drop(full_rate);
    }
    else
    {
        this->fetch_next();
        if (!this->next_iter_buffer.empty())
        {
            this->next(t, site_id, largest_demand);
        }
        else
        {
            t = -1;
            site_id = -1;
            largest_demand = 0;
            return;
        }
    }
}

void SiteLargestTDemandManager::fetch_next()
{
    int t = -1;
    int site_id = -1;
    double max_std_v = -100000.0;
    for (int _site_id = 0; _site_id < N; _site_id++)
    {
        if (this->site_big_bw_remained_count[_site_id] < 0)
        {
            cout << "error: this->site_big_bw_remained_count[_site_id] < 0" << endl;
            throw exception();
        }
        if (!this->site_big_bw_remained_count[_site_id])
        {
            continue;
        }

        _HeapNode *head = this->site_largest_tdemand_updater[_site_id]->head();
        int demand_bw = head->value;
        double bw_upper = site_info.site_bw_upper[_site_id];
        double full_rate = min(demand_bw / bw_upper, 1.0);

        StdNormalizer *normalizer = this->site_demand_normalizer[_site_id];
        double std_v = normalizer->transform(full_rate);
        if (std_v > max_std_v)
        {
            max_std_v = std_v;
            site_id = _site_id;
            t = head->t;
        }
    }

    if (site_id == -1)
    {
        return;
    }

    AssignFlag &t_assign_flag = this->assign_state_vec->at(t)->site_big_bw_flag_arr[site_id];
    int next_t = t + 1;
    if (next_t == T)
    {
        switch (t_assign_flag)
        {
        case CAREFUL:
            t_assign_flag = RADICAL;
            this->site_big_bw_remained_count[site_id]--;
            this->next_iter_buffer.push_back(make_tuple(t, site_id));
            break;
        case BUFFER:
            t_assign_flag = RADICAL;
            this->next_iter_buffer.push_back(make_tuple(t, site_id));
            break;
        case RADICAL:
            cout << "code error: reassign RADICAL" << endl;
            throw exception();
            break;
        }
        return;
    }
    AssignFlag &next_t_assign_flag = this->assign_state_vec->at(next_t)->site_big_bw_flag_arr[site_id];

    if ((t_assign_flag == CAREFUL) && (next_t_assign_flag == CAREFUL))
    {
        if (this->site_big_bw_remained_count[site_id] == 1)
        {
            t_assign_flag = BUFFER;
            this->site_big_bw_remained_count[site_id]--;
            this->fetch_next();
        }
        else
        {
            t_assign_flag = RADICAL;
            next_t_assign_flag = BUFFER;
            this->site_big_bw_remained_count[site_id] -= 2;
            this->next_iter_buffer.push_back(make_tuple(t, site_id));
        }
        return;
    }
    if ((t_assign_flag == CAREFUL) && (next_t_assign_flag == RADICAL))
    {
        t_assign_flag = RADICAL;
        this->site_big_bw_remained_count[site_id]--;
        this->next_iter_buffer.push_back(make_tuple(t, site_id));
        return;
    }
    if ((t_assign_flag == BUFFER) && (next_t_assign_flag == CAREFUL))
    {
        t_assign_flag = RADICAL;
        next_t_assign_flag = BUFFER;
        this->site_big_bw_remained_count[site_id]--;
        this->next_iter_buffer.push_back(make_tuple(t, site_id));
        return;
    }
    if ((t_assign_flag == BUFFER) && (next_t_assign_flag == RADICAL))
    {
        t_assign_flag = RADICAL;
        this->next_iter_buffer.push_back(make_tuple(t, site_id));
        return;
    }
}

void SiteLargestTDemandManager::decrease_demand_heap(int t, int (&site_demand_decrement)[MAX_N])
{
    for (int site_id = 0; site_id < N; site_id++)
    {
        if (!(this->site_big_bw_remained_count[site_id]))
        {
            continue;
        }
        if (!site_demand_decrement[site_id])
        {
            continue;
        }

        int decrement = site_demand_decrement[site_id];
        if (this->assign_state_vec->at(t)->site_expanded_near_radical[site_id])
        {
            decrement += decrement * this->expansion_rate_near_radical;
        }

        LargestUpdater *largest_updater = this->site_largest_tdemand_updater[site_id];
        int old_demand = largest_updater->at(t)->value;
        int new_demand = old_demand - decrement;

        double bw_upper = site_info.site_bw_upper[site_id];
        double old_full_rate = min(old_demand / bw_upper, 1.0);
        double new_full_rate = min(new_demand / bw_upper, 1.0);

        StdNormalizer *normalizer = this->site_demand_normalizer[site_id];
        normalizer->drop(old_full_rate).add(new_full_rate);

        largest_updater->update(t, -decrement);
    }
}

void SiteLargestTDemandManager::increase_inherit_to_next_t(int t, int site_id, int site_allo_bw)
{
    if (!(this->site_big_bw_remained_count[site_id]))
    {
        return;
    }
    LargestUpdater *largest_updater = this->site_largest_tdemand_updater[site_id];

    int next_t = t + 1;
    if (next_t < T)
    {
        if (!largest_updater->is_poppid(next_t))
        {
            int old_demand = largest_updater->at(next_t)->value;
            int increment = (int)(old_demand * this->expansion_rate_near_radical) + (int)(site_allo_bw * INHERIT_RATE);
            int new_demand = old_demand + increment;

            double bw_upper = site_info.site_bw_upper[site_id];
            double old_full_rate = min(old_demand / bw_upper, 1.0);
            double new_full_rate = min(new_demand / bw_upper, 1.0);

            StdNormalizer *normalizer = this->site_demand_normalizer[site_id];
            normalizer->drop(old_full_rate).add(new_full_rate);

            largest_updater->update(next_t, increment);
            this->assign_state_vec->at(next_t)->site_expanded_near_radical[site_id] = true;
        }
    }
    int pre_t = t - 1;
    if (pre_t >= 0)
    {
        if (!largest_updater->is_poppid(pre_t))
        {
            int old_demand = largest_updater->at(pre_t)->value;
            int increment = (int)(old_demand * this->expansion_rate_near_radical);
            int new_demand = old_demand + increment;

            double bw_upper = site_info.site_bw_upper[site_id];
            double old_full_rate = min(old_demand / bw_upper, 1.0);
            double new_full_rate = min(new_demand / bw_upper, 1.0);

            StdNormalizer *normalizer = this->site_demand_normalizer[site_id];
            normalizer->drop(old_full_rate).add(new_full_rate);

            largest_updater->update(pre_t, increment);
            this->assign_state_vec->at(pre_t)->site_expanded_near_radical[site_id] = true;
        }
    }
}

void SiteLargestTDemandManager::clear_site(int site_id)
{
    this->site_big_bw_remained_count[site_id] = 0;
}
//////////////////////////////////////////////////////////////////////////////////////
// 假设把流量分配给某个边缘节点，带宽占上限的比例
double _rate_if_assign(TAssign *tassign, TAssignState *tassign_state, int stream_id, int demand_bw, int site_id)
{
    double bw_upper = site_info.site_bw_upper[site_id];

    int old_edge_site_bw = tassign->site_total_bw[site_id];
    int new_edge_site_bw = old_edge_site_bw + demand_bw;

    if (new_edge_site_bw <= config_info.base_cost)
    {
        return 0.0;
    }

    AssignFlag &assign_flag = tassign_state->site_big_bw_flag_arr[site_id];

    if ((assign_flag == RADICAL) && (new_edge_site_bw <= bw_upper)) // 如果极端分配节点的带宽有剩余且足够，则比例为0
    {
        return 0.0;
    }

    if ((assign_flag == BUFFER) && (new_edge_site_bw <= bw_upper))
    {
        if (!tassign->next_tassign) // 最后一个时刻不需要考虑继承流量
        {
            return 0.0;
        }
        else
        {
            int next_t_total_bw = tassign->next_tassign->site_allocated_bw[site_id] + new_edge_site_bw * INHERIT_RATE;
            if (next_t_total_bw <= config_info.base_cost)
            {
                return 0.0;
            }
            else
            {
                return next_t_total_bw / bw_upper;
            }
        }
    }

    return new_edge_site_bw / bw_upper;
}
//////////////////////////////////////////////////////////////////////////////////////
// end: 前置工具
//////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////////
// start: 生成初始解
//////////////////////////////////////////////////////////////////////////////////////

// 先按流的总和从大到小排序，再按流内从大到小排序，以此优先顺序分配极端分配节点
void _radical_assign_t(int (&site_demand_decrement)[MAX_N], int &site_allo_bw,
                       int t, int site_id, int largest_demand, int min_stream,
                       AssignInfo &assign_info, vector<TAssignState *> &assign_state_vec)
{
    TAssignState *tassign_state = assign_state_vec[t];
    TDemand *tdemand = demand_info.demand_vec[t];
    TAssign *tassign = assign_info.assign_vec[t];
    tassign->refresh_inherited_bw();
    tassign->refresh_total_bw();
    const int &P = tassign->P;

    int site_bw_upper = site_info.site_bw_upper[site_id];
    // 先预留0.05的流量不分配，避免前后两个时刻都是极端分配节点时溢出过多
    int site_remained_bw = ((int)(site_bw_upper * (1.0 - INHERIT_RATE))) - tassign->site_total_bw[site_id];

    int reachable_stream_bw_sum[P] = {0}; // 计算站点可达的stream带宽的和
    for (auto &client_id : site_info.site_to_clients[site_id])
    {
        for (int stream_id = 0; stream_id < P; ++stream_id)
        {
            const AlloNode &allo_node = tassign->stream_client_to_allo_node[stream_id][client_id];
            const int &demand_bw = allo_node.bandwidth;

            if (demand_bw <= min_stream) //小流量先不分配
            {
                continue;
            }
            if (site_remained_bw < demand_bw) // 放不下的先不分配
            {
                continue;
            }
            if (allo_node.site_id != -1) // 如果该流已经被分配过了，则跳过
            {
                continue;
            }
            reachable_stream_bw_sum[stream_id] += demand_bw;
        }
    }
    vector<int> stream_bw_sorted_index = arg_sort(reachable_stream_bw_sum, P, false); //按流的大小从大到小排序

    for (auto &stream_id : stream_bw_sorted_index)
    {
        int stream_bw_sum = reachable_stream_bw_sum[stream_id];
        if (!stream_bw_sum)
        {
            break;
        }

        for (auto &demand_bw_node : tdemand->sorted_stream_deamnd_bw[stream_id])
        {
            const int &demand_bw = demand_bw_node.bandwidth;
            if (demand_bw <= min_stream) //小流量先不分配
            {
                break;
            }
            if (site_remained_bw < demand_bw)
            {
                continue;
            }

            const int &client_id = demand_bw_node.client_id;
            if (!site_info.site_reachable_matrix[site_id][client_id])
            { //不可达，跳过
                continue;
            }

            // 如果该流已经被分配过了，则跳过
            if (tassign->stream_client_to_allo_node[stream_id][client_id].site_id != -1)
            {
                continue;
            }

            tassign->add_allocate(stream_id, client_id, site_id);
            site_remained_bw -= demand_bw;
            site_allo_bw += demand_bw;

            for (auto &adjacent_site_id : client_info.client_to_sites[client_id])
            {
                if (tassign_state->site_big_bw_flag_arr[adjacent_site_id] != RADICAL)
                {
                    site_demand_decrement[adjacent_site_id] += demand_bw;
                }
            }
        }
    }
}

void _radical_assign_all(AssignInfo &assign_info, vector<TAssignState *> &assign_state_vec, int min_stream, double expansion_rate_near_radical, int big_bw_drop_num)
{
    SiteLargestTDemandManager site_largest_tdemand_manager(&assign_state_vec, min_stream, expansion_rate_near_radical, big_bw_drop_num);

    int t, site_id, largest_demand;
    site_largest_tdemand_manager.next(t, site_id, largest_demand);

    int site_demand_decrement[MAX_N]; // 分配一个极端节点后，同时刻其他节点的带宽量会降低，这里记录的是降低的量，大于等于0
    int site_allo_bw;                 // 记录当前站点分配出去的极端配分流量，用于计算继承流量并加入到下一时刻上去
    while (t != -1)
    {
        if (!largest_demand) //如果服务器的最大请求量为0，则将该站点跳过，后面取最大时不考虑它
        {
            site_largest_tdemand_manager.clear_site(site_id);
        }
        else
        {
            fill(site_demand_decrement, site_demand_decrement + MAX_N, 0);
            site_allo_bw = 0;

            _radical_assign_t(site_demand_decrement, site_allo_bw, t, site_id, largest_demand, min_stream, assign_info, assign_state_vec);

            site_largest_tdemand_manager.decrease_demand_heap(t, site_demand_decrement);
            site_largest_tdemand_manager.increase_inherit_to_next_t(t, site_id, site_allo_bw);
        }
        site_largest_tdemand_manager.next(t, site_id, largest_demand);
    }
}
//////////////////////////////////////////////////////////////////////////////////////
void _low_rate_first_assign_t(int t, AssignInfo &assign_info, vector<TAssignState *> &assign_state_vec)
{
    TDemand *tdemand = demand_info.demand_vec[t];
    TAssign *tassign = assign_info.assign_vec[t];
    TAssignState *tassign_state = assign_state_vec[t];
    tassign->refresh_inherited_bw();
    tassign->refresh_total_bw();

    for (auto &demand_bw_node : tdemand->sorted_deamnd_bw) //已经是按照带宽需求从大到小排序的
    {
        if (!demand_bw_node.bandwidth)
        {
            break;
        }
        const int &client_id = demand_bw_node.client_id;
        const int &stream_id = demand_bw_node.stream_id;
        const int &demand_bw = demand_bw_node.bandwidth;

        // 如果该流已经被分配过了，则跳过
        if (tassign->stream_client_to_allo_node[stream_id][client_id].site_id != -1)
        {
            continue;
        }

        int selected_site_id = -1;
        double min_rate = 100;
        for (auto &site_id : client_info.client_to_sites[client_id])
        {
            if (site_info.site_bw_upper[site_id] < demand_bw)
            {
                continue;
            }
            double rate = _rate_if_assign(tassign, tassign_state, stream_id, demand_bw, site_id); // 带宽占上限的比例，比例最小原则分配流量
            if (rate < min_rate)
            {
                min_rate = rate;
                selected_site_id = site_id;
            }
        }

        if (selected_site_id == -1)
        {
            //找不到合适的site_id，这种情况不应该出现，可能是数据中出现了无解的情况
            cout << "ERROR: selected_site_id == -1" << endl;
            throw exception();
        }

        tassign->add_allocate(stream_id, client_id, selected_site_id);
    }
}

void _low_rate_first_assign_all(AssignInfo &assign_info, vector<TAssignState *> &assign_state_vec)
{
    for (int t = 0; t < T; ++t)
    {
        _low_rate_first_assign_t(t, assign_info, assign_state_vec);
    }
}
//////////////////////////////////////////////////////////////////////////////////////
double _get_edge_site_score(const int &edge_site_bw, const int &site_bw_upper, int lambda)
{
    if (edge_site_bw == 0)
    {
        return 0.0;
    }
    else
    {
        double full_rate = ((double)edge_site_bw) / site_bw_upper;
        return lambda * full_rate * edge_site_bw + edge_site_bw;
    }
}

double _score_of_edge_site(TAssign *tassign, int edge_site_bw, int site_id, int bw_upper, AssignFlag &assign_flag, int lambda)
{
    if (edge_site_bw > bw_upper)
    {
        return _get_edge_site_score(edge_site_bw, bw_upper, lambda);
    }

    switch (assign_flag)
    {
    case CAREFUL:
        return _get_edge_site_score(edge_site_bw, bw_upper, lambda);
        break;
    case BUFFER:
    {
        if (tassign->next_tassign)
        {
            int next_t_total_bw = tassign->next_tassign->site_allocated_bw[site_id] + edge_site_bw * INHERIT_RATE;
            return _get_edge_site_score(next_t_total_bw, bw_upper, lambda);
        }
        else
        {
            return 0.0;
        }
        break;
    }
    case RADICAL:
        return 0.0;
        break;
    }
    return _get_edge_site_score(edge_site_bw, bw_upper, lambda);
}

// 假设把流量分配给某个边缘节点，则分数的增长量
double _score_increase_if_assign(TAssign *tassign, TAssignState *tassign_state, int stream_id, int demand_bw, int site_id, int lambda)
{
    double score_increase = 0.0;
    const int &largest_bw = tassign->site_stream_to_allo_info[site_id][stream_id].largest_bw;

    if (demand_bw > largest_bw)
    {
        const long long &old_center_site_bw = tassign->center_site_bw;
        long long new_center_site_bw = old_center_site_bw + (demand_bw - largest_bw);
        score_increase += get_center_site_score(new_center_site_bw) - get_center_site_score(old_center_site_bw);
    }

    int &old_edge_site_bw = tassign->site_total_bw[site_id];
    int new_edge_site_bw = old_edge_site_bw + demand_bw;
    int &bw_upper = site_info.site_bw_upper[site_id];
    AssignFlag &assign_flag = tassign_state->site_big_bw_flag_arr[site_id];

    double old_edge_site_score = _score_of_edge_site(tassign, old_edge_site_bw, site_id, bw_upper, assign_flag, lambda);
    double new_edge_site_score = _score_of_edge_site(tassign, new_edge_site_bw, site_id, bw_upper, assign_flag, lambda);

    score_increase += (new_edge_site_score - old_edge_site_score);
    return score_increase;
}

void _low_score_first_assign_t(int t, AssignInfo &assign_info, vector<TAssignState *> &assign_state_vec, int lambda)
{
    TDemand *tdemand = demand_info.demand_vec[t];
    TAssign *tassign = assign_info.assign_vec[t];
    TAssignState *tassign_state = assign_state_vec[t];

    tassign->refresh_inherited_bw();
    tassign->refresh_total_bw();

    for (auto &demand_bw_node : tdemand->sorted_deamnd_bw) //已经是按照带宽需求从大到小排序的
    {
        if (!demand_bw_node.bandwidth)
        {
            break;
        }
        const int &client_id = demand_bw_node.client_id;
        const int &stream_id = demand_bw_node.stream_id;
        const int &demand_bw = demand_bw_node.bandwidth;

        // 如果该流已经被分配过了，则跳过
        if (tassign->stream_client_to_allo_node[stream_id][client_id].site_id != -1)
        {
            continue;
        }

        int selected_site_id = -1;
        double min_score = 1e100;
        for (auto &site_id : client_info.client_to_sites[client_id])
        {
            if (site_info.site_bw_upper[site_id] < demand_bw)
            {
                continue;
            }
            double _score = _score_increase_if_assign(tassign, tassign_state, stream_id, demand_bw, site_id, lambda); // 分数的增长
            if (_score < min_score)
            {
                min_score = _score;
                selected_site_id = site_id;
            }
        }

        if (selected_site_id == -1)
        {
            //找不到合适的site_id，这种情况不应该出现，可能是数据中出现了无解的情况
            cout << "ERROR: selected_site_id == -1" << endl;
            throw exception();
        }

        tassign->add_allocate(stream_id, client_id, selected_site_id);
    }
}

void _low_score_first_assign_all(AssignInfo &assign_info, vector<TAssignState *> &assign_state_vec, int lambda)
{
    for (int t = 0; t < T; ++t)
    {
        _low_score_first_assign_t(t, assign_info, assign_state_vec, lambda);
    }
}

//////////////////////////////////////////////////////////////////////////////////////
void _process_overflow_all(AssignInfo &assign_info)
{
    for (auto &tassign : assign_info.assign_vec)
    {
        process_overflow_t(tassign);
    }
}

//////////////////////////////////////////////////////////////////////////////////////
// end: 生成初始解
//////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////////
// start: 绘图
//////////////////////////////////////////////////////////////////////////////////////

// 打印初解统计指标和输出图形，以寻找可能的优化点
void insight_solution(AssignInfo &assign_info, vector<TAssignState *> &assign_state_vec)
{
    // long long big_bw[MAX_N] = {0};
    // for (int t = 0; t < T; t++)
    // {
    //     TAssign *tassign = assign_info.assign_vec[t];
    //     for (int site_id = 0; site_id < N; site_id++)
    //     {
    //         AssignFlag &flag = assign_state_vec[t]->site_big_bw_flag_arr[site_id];
    //         if ((flag == RADICAL))
    //         {
    //             big_bw[site_id] += tassign->site_allocated_bw[site_id];
    //         }
    //     }
    // }
    // long long radical_sum = sum_of<long long>(big_bw, big_bw + MAX_N);
    // cout << radical_sum << endl;
    // for (int site_id = 0; site_id < N; site_id++)
    // {
    //     cout << site_id << ":" << big_bw[site_id] << "," << endl;
    // }

    // plot_line(big_bw, big_bw + MAX_N);
}

//////////////////////////////////////////////////////////////////////////////////////
// end: 绘图
//////////////////////////////////////////////////////////////////////////////////////

AssignInfo init_solution()
{
    AssignInfo assign_info(demand_info);
    vector<TAssignState *> assign_state_vec = _init_assign_state_vec();

    _radical_assign_all(assign_info, assign_state_vec, 0, 0.5, 0);

    // 按照打满比例低的优先，不考虑中心节点
    _low_rate_first_assign_all(assign_info, assign_state_vec);

    // 考虑中心节点，参数lambda用来均衡边缘节点和中心节点的损失，参数lambda对结果的影响太敏感，很难调试
    // _low_score_first_assign_all(assign_info, assign_state_vec, 10.0);

    _process_overflow_all(assign_info);

    // insight_solution(assign_info, assign_state_vec);

    return assign_info;
}
